# Apriori算法
"""
由于Apriori算法假定项集中的项是按字典序排序的，而集合本身是无序的，所以我们在必要时需要进行set和list的转换；
由于要使用字典（support_data）记录项集的支持度，需要用项集作为key，而可变集合无法作为字典的key，因此在合适时机应将项集转为固定集合frozenset。
"""
 
 
class apriori_algorithm:
 
    # 算法初始化
    def __init__(self, minSupport, dataSet):
        """
            dataSet的形式是列表，列表中的元素还是列表，如[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
        """
        self.minSupport = minSupport  # 最小支持度
        self.dataSet = dataSet  # 数据集

    def generate_C1(self, dataSet):
        """
            生成单个元素的项集列表
            参数：
                data_set：数据集
            返回值：
                C1: 单个元素的项集列表
        """
        C1 = []  # 用于存放生成的单个物品的项集列表
        # 遍历数据集
        for data in dataSet:
            for item in data:
                if [item] not in C1:
                    C1.append([item])
        C1.sort()
        return C1
 
    # 遍历数据集，和Ck对比，计数
    def generateLk_by_Ck(self, dataSet, Ck, minSupport, support_data):
        """
           通过“剪枝”，从候选频繁项集中得到频繁项集
           参数:
               data_set: 数据集
               Ck: 候选频繁项集列表
               min_support: 要求的最小支持度
               support_data: 字典类型，键是频繁项集，值是支持度
           返回值:
               Lk: 频繁项集列表
        """
        D = map(set, dataSet)
        C = map(frozenset, Ck)
        #set()和frozenset()都是python3的内置函数，都是将数据类型转变为集合(set)类型，其中frozenset()表示的是一个冻结的集合，是不可变的，存在hash值，可以作为字典的键
        C1 = list(C)  # 关于map对象的遍历，在内循环中遍历完最后一个元素后，再次访问时会放回空列表，所以外循环第二次进入的时候是空的，需要将其转为list处理
        countData = dict()
        for d in D:  # set遍历
            for c in C1:
                if c.issubset(d):  # 子集判断，并非元素判断
                    if c not in countData.keys():  # 将集合作为字典的键使用,c为[]型
                        countData[c] = 1
 
                    else:
                        countData[c] += 1
 
        numItems = float(len(list(dataSet)))
        returnList = []
        # 遍历前面得到的计数字典
        for key in countData:
            support = countData[key] / numItems
            if support >= minSupport:
                returnList.insert(0, key)  # insert() 函数用于将指定对象插入列表的指定位置
                support_data[key] = support
 
        return returnList
 
    def generate_Lk(self, dataSet, k, min_support):
        """
           生成所有频繁项集（项集中的元素个数从1~k的所有频繁项集）
           参数:
               data_set:数据集
               k: 频繁项集中含有的最多的元素
               min_support: 最小支持度
           返回值:
               L: 出现的所有频繁项集
               support_data: 每个频繁项集对应的支持度
        """
        support_data = {}
        C1 = self.generate_C1(dataSet)
        L1 = self.generateLk_by_Ck(dataSet, C1, min_support, support_data)
        Lksub1 = L1.copy()
 
        L = []
        L.append(Lksub1)
 
        for i in range(2, k + 1):
            Ci = self.generate_Ck(Lksub1, i)
            Li = self.generateLk_by_Ck(dataSet, Ci, min_support, support_data)
            Lksub1 = Li.copy()
            L.append(Lksub1)
        return L, support_data
 
    def generate_Ck(self, Lk, k):
        """
            产生候选频繁项集
            参数：
                LK：包含k-1个元素的频繁项集的列表
                k：项集中元素个数
            返回值：
                CK：包含k个元素的候选频繁项集列表
        """
        Ck = list()
        len_Lk = len(list(Lk))
        list_Lk = list(Lk) 
        for i in range(len_Lk):
            for j in range(i, len_Lk):
                l1 = list(list_Lk[i])
                l2 = list(list_Lk[j])
                l1.sort()
                l2.sort()
                if l1[0:k - 2] == l2[0:k - 2]:
                    Ck_item = list_Lk[i] | list_Lk[j]
                    if self.isCk(Ck_item, list_Lk):
                        Ck.append(Ck_item)
                    # Ck.add(Ck_item)
        return Ck
 
    def isCk(self, Ck_item, list_Lk):
        """
            判断某个项集是否为频繁项集，利用的原理是如果一个项集是频繁项集，则它的所有子集都是频繁项集
            参数：
                Ck_item：某个含有k个元素的项集
                list_Lk：含有k-1个元素的频繁项集的列表
            返回值：
                True表示是频繁项集，False表示不是频繁项集
        """
        for item in Ck_item:
            sub_Ck = Ck_item - frozenset([item])
            if sub_Ck not in list_Lk:
                return False
        return True
 
    # 生成关联规则
    def generate_big_rules(self, L, support_data, min_conf):
        """
            从频繁项集中找到关联规则
            参数:
                L: 所有频繁项集的列表
                support_data: 每个频繁项集对应的支持度
                min_conf: 最小可信度
            返回值：
                big_rule_list：规则列表
        """
        big_rule_list = []
        sub_set_list = []
        for i in range(0, len(L)):
            for freq_set in L[i]:
                for sub_set in sub_set_list:
                    if sub_set.issubset(freq_set):
                        conf = support_data[freq_set] / support_data[freq_set - sub_set]
                        big_rule = (freq_set - sub_set, sub_set, conf)
 
                        if conf >= min_conf and big_rule not in big_rule_list:
                            print(freq_set - sub_set, " => ", sub_set, "conf: ", conf)
                            big_rule_list.append(big_rule)
                sub_set_list.append(freq_set)
        return big_rule_list
 

def getUpPlateList(fileName):
    import csv
    with open(fileName,"r",encoding = "utf-8") as inFile:
        upPlateList = []
        csvReader = csv.reader(inFile)
        plateName = next(csvReader)
        for days in csvReader:
            dailyUpPlateList = []
            for i in range(1,len(days)):
                if float(days[i]) == 1:
                    dailyUpPlateList.append(plateName[i])
            upPlateList.append(dailyUpPlateList)
        return upPlateList

 
if __name__ == '__main__':
    minS = 0.3
    dataSet = getUpPlateList("Data.csv")
    apriori = apriori_algorithm(minSupport=minS, dataSet=dataSet)
    L, support_data = apriori.generate_Lk(dataSet, 6, minS)
 
    print(L)
    print(support_data)
    big_rule_list = apriori.generate_big_rules(L, support_data, 0.5)
